//1.好多额外数组（额外空间）
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> temp1={1} ;
        vector<int> temp2={1} ;
        vector<int> answer;
        int temp =1;
        for(int i = 0; i< nums.size()-1; ++i) {
            temp *= nums[i];
            temp1.push_back(temp);
        }
        temp =1;
        for(int i = nums.size()-1; i> 0; --i) {
            temp *= nums[i];
            temp2.push_back(temp);
        }
        reverse(temp2.begin(), temp2.end());
        for(int i =0;i<temp1.size();++i) {
            answer.push_back(temp1[i]*temp2[i]);
        }
        return answer;
    }
};

//2.只有两个数组，四次遍历太多了
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {

        vector<int> answer={1};
        int temp =1;
        for(int i = 0; i< nums.size()-1; ++i) {
            //计算前缀和
            temp *= nums[i];
            answer.push_back(temp);
        }
        temp =1;

        for(int i = nums.size()-1; i> 0; --i) {
           //计算后缀和
            temp *= nums[i];
            nums[i] = temp;
        }
        
        for(int i = 0; i< nums.size()-1; ++i) {
            nums[i] = nums[i+1];
            //修改后缀和位置
        }
        nums[nums.size()-1]=1;

        for(int i =0;i<answer.size();++i) {
            answer[i] = answer[i]*nums[i];
            //得到结果
        }
        return answer;
    }
};

//3.操作次数更少
/*
nums=[1,2,3,4]
前缀完之后 answer = [1,1,2,6]
计算后缀乘积并直接与前缀乘积相乘
先计算4的后缀乘积,
4的右边为1，4的前缀乘积为6，6*1=6；
3的右边为4，3的前缀乘积为2，2*4=8；
2的右边为12，2的前缀乘积为1，1*12=12；
1的右边为24，1的前缀乘积为1，1*24=24；
*/

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);
        
        // 计算前缀乘积
        int prefix = 1;
        for (int i = 0; i < n; ++i) {
            answer[i] = prefix;
            prefix *= nums[i];
        }

        
        // 计算后缀乘积并直接与前缀乘积相乘
        int suffix = 1;
        for (int i = n - 1; i >= 0; --i) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        
        return answer;
    }
};

